CF 2067 div. 1+2

📅Date: 2025-02-15 📚Category: 算法竞赛 📂Tags: Codeforces div1 div2 📑Word: 6.9k

A Adjacent Digit Sums

题目大意

给你两个数字 \(x, y\). 你需要判断是否存在一个整数 \(n\), 使得 \(S(n) = x\), \(S(n + 1) = y\).

这里, \(S(a)\) 表示十进制数 \(a\) 的数位之和.

题解

显然有解当且仅当 \(y=x+1\) 或 \((x-y+1)\equiv 0 (\bmod 9)\wedge x>y\)

代码

int T,x,y;

int main()
{
    read(T);
    while(T--)
    {
        read(x),read(y);
        if(y-x==1)puts("YES");
        else if(x>y && (x-y+1)%9==0)puts("YES");
        else puts("NO");
    }
    flushout();
    return 0;
}

B Two Large Bags

题目大意

你有两大袋数字. 最初, 第一个袋子里有 \(n\) 个数字: \(a_1, a_2, \ldots, a_n\), 而第二个袋子是空的. 您可以进行以下操作:

  • 从第一个数字袋中选择任意一个数字并将其移动到第二个数字袋中.
  • 从第一个袋子中选择一个第二个袋子中也有的数字, 并将其增加一 (只对第一个袋子中的数加).

这两种操作的次数不限, 顺序不限. 有可能使第一个和第二个袋子中的内容完全相同吗?

题解

根据题述操作, 当某一类数个数超过 2 个时, 我们选择保留两个数并将其它数都 +1 显然不会使整个状态更劣. 因为我们的目的是让每种数的个数都是偶数个, 而该操作会让当前数变得合法, 且可能和后面的数配对.

所以我们从小到大枚举依次往后加即可. 最后判断是否还存在数字是奇数个.

代码

const int N = 1e3 + 10;
int T, n, cnt[N];

int main()
{
    read(T);
    while (T--)
    {
        read(n);
        for (int i = 1; i <= n + 1; i++)
            cnt[i] = 0;
        for (int i = 1, v; i <= n; ++i)
            read(v), cnt[v]++;
        for (int i = 1; i <= n; i++)
            if (cnt[i] > 2)
                cnt[i + 1] += cnt[i] - 2, cnt[i] = 2;
        bool flag = true;
        for (int i = 1; i <= n + 1; i++)
            if (cnt[i] & 1)
                flag = false;
        puts(flag ? "YES" : "NO");
    }
    flushout();
    return 0;
}

C Devyatkino

题目大意

给你一个正整数 \(n\). 在一次运算中, 你可以将十进制表示只包含数字 \(9\) 的任何正整数加到 \(n\) 中, 而且可能重复多次.

要使数字 \(n\) 的十进制表示中至少包含一位数字 \(7\), 至少需要多少次运算?

例如, 如果是 \(n = 80\), 只需进行一次运算即可：在运算 \(n = 179\) 之后, 将 \(99\) 加到 \(n\) 中, 其中包含数字 \(7\).

题解

不太能严格证明, 首先答案肯定不会超过 9, 因为你只 +9 也一定能在 9 步内完成. 猜测最少步数只会进行同一种操作, 即每次加的数都是同一个数, 直觉是加小的数不一定会产生进位可能会没用, 加更大的数连该数一起变也没啥用. 但不会证.

代码

const ll v[10]={3,4,5,6,7,8,9,0,1,2};
ll T,n;
bool check(ll nn)
{
    while(nn)
    {
        if(nn%10==7)return 1;
        nn/=10;
    }
    return 0;
}
int main()
{
    read(T);
    while(T--)
    {
        read(n);
        ll nn = n,flag = 0,pw=1;
        while(nn)
        {
            if(nn%10==7)flag=1;
            nn/=10;
        }
        if(flag)
        {
            wt_str("0\n");
            continue;
        }
        ll ans = v[n%10],cnt = 0;
        for(int i=1;i<=15;i++)
        {
            pw*=10;
            cnt=0;
            nn = n;
            while(cnt<ans)
            {
                nn+=pw-1;
                cnt++;
                if(check(nn))
                {
                    ans=min(ans,cnt);
                    break;
                }
            }
        }
        write(ans);
    }
    flushout();
    return 0;
}

D Object Identification

题目大意

交互题

这是一个互动问题.

给你一个由 \(1\) 到 \(n\) 的整数组成的数组 \(x_1, \ldots, x_n\). 评审团还有一个由 \(1\) 至 \(n\) 的整数组成的固定但隐藏的数组 \(y_1, \ldots, y_n\). 数组 \(y\) 中的元素是不知道的. 此外, 已知所有 \(i\) 、 \(x_i \neq y_i\) 和所有成对的 \((x_i, y_i)\) 都是不同的.

陪审团秘密地想到了两个对象中的一个, 你需要确定是哪一个：

  • 对象 A：一个有向图, 有 \(n\) 个顶点, 编号从 \(1\) 到 \(n\), 有 \(n\) 条形式为 \(x_i \to y_i\) 的边.
  • 对象 B：坐标平面上的 \(n\) 个点. \(i\) th点的坐标为 \((x_i, y_i)\).

要猜测陪审团想到了哪个对象, 您可以进行查询. 在一个查询中, 您必须指定两个数字 \(i, j\). \((1 \leq i, j \leq n, i \neq j)\). 作为回应, 您将收到一个数字：

  • 如果评委想到了对象 A, 您将收到图中从顶点 \(i\) 到顶点 \(j\) 的最短路径长度(以边为单位), 如果没有路径, 则收到 \(0\).
  • 如果评委想到了物体 B, 则得到点 \(i\) 和 \(j\) 之间的曼哈顿距离, 即 \(|x_i -x_j| + |y_i - y_j|\).

你有 \(2\) 个查询来确定陪审团想到了哪个对象.

题解

切入口就是 \(A\) 类返回 \(0\), 因为当 \(B\) 类时返回值一定非负, 所以当 \(x_i\) 不是全排列时, 直接询问没出现过的数到其余任何位置, 如果返回 \(0\) 就是 \(A\), 否则是 \(B\).

而当 \(x_i\) 是排列时, 我们直接找 1 和 n 两个 \(x_i\) 的位置, 因为 \(A\) 类的返回值肯定小于等于 \(n-1\), 而如果是 \(B\) 类时, 询问这两个位置返回值最小就是 \(n-1\). 但也存在相等即均为 \(n-1\) 的情况. 这时候就需要问第二次, 而我们只需要简单的交换 \(i,j\) 再次询问即可. 只需要检测第二次询问的值是不是等于 \(n-1\) 即可.

代码

const int N = 2e5 + 10;
int T, n, x[N], mp[N];

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> n;
        memset(mp, 0, sizeof(int) * (n + 1));
        for (int i = 1; i <= n; i++)
            cin >> x[i];
        for (int i = 1; i <= n; i++)
            mp[x[i]]++;
        int res1 = -1, res2 = 0, mn = 0, mx = 0,flag=0;
        for (int i = 1; i <= n; i++)
        {
            if (!mp[i])
            {
                cout << "? " << i << ' ' << (i < n ? i + 1 : i - 1) << endl;
                cin >> res1;
                if(res1) cout<<"! B"<<endl;
                else cout<<"! A"<<endl;
                flag=1;
                break;
            }
            if (!mn && mp[i])
                mn = i;
            if (mp[i])
                mx = i;
        }
        if(flag)continue;
        for (int i = 1; i <= n; i++)
            if (mn == x[i])
            {
                mn = i;
                break;
            }
        for (int i = 1; i <= n; i++)
            if (mx == x[i])
            {
                mx = i;
                break;
            }
        cout << "? " << mn << ' ' << mx << endl;
        cin >> res1;
        cout << "? " << mx << ' ' << mn << endl;
        cin >> res2;
        if (res1==res2&&res1>=n-1)
            cout << "! B" << endl;
        else
            cout << "! A" << endl;
    }
    flushout();
    return 0;
}

评论